In such a system, the bridge is responsible for establishing whether the data reaching the bridge from a node in the first network is transmitted to a different node in the same network and is therefore discarded by the bridge or, alternatively, is to be passed to the second network. Furthermore, in the event that data is to be passed from one network to the other, the bridge is also responsible for translating the data from the protocol of the first network to the protocol of the second network.
In order to determine whether data is to be rejected (i.e. transmitted to a different node in the first network) or is to be passed to the second network, the data must include a source address and a destination address corresponding, respectively, to an address of a node in the source network and an address of a node in the destination network. Thus, if this data points to nodes in different networks, then the bridge must pass the data from one network to the other; whilst if the source and destination addresses point to nodes in the same network, the data obviously does not need to be passed by the bridge. In such network systems, there is associated with the bridge a look-up table for storing therein addresses associated with nodes in one of the networks, whereby suitable logic associated with the bridge may determine whether the data is to be rejected or passed by the bridge according to the destination address associated with the data.
It will be apparent that two different approaches may be adopted when determining what is to be done with the data. According to both approaches, the destination address associated with data reaching the bridge is looked up in the look-up table within the bridge and, if found therein, permits data either to be rejected by the bridge or, alternatively, to be passed through the bridge to the other network, according to whether the source and destination addresses point to the same or different networks.
The two approaches differ in the event that a particular destination address is not found in the look-up table. In accordance with a first approach, the addresses stored in the look-up table correspond to the addresses of each node in the receiving network. In this case, if the destination address associated with data reaching the bridge is not found in the look-up table, this indicates that data is not to be passed through the bridge, it being assumed that the addresses associated with all nodes in the receiving network are known to the look-up table. This approach is called "positive filtering" since the bridge, in effect, filters out any data whose destination address is not known to the look-up table and prevents such data from being passed therethrough.
The disadvantages with so-called "positive filtering" networks are that they are protocol dependent and space-limited. Therefore, so-called "negative filtering" bridges are employed wherein the addresses associated with all nodes in the sending network are stored in the look-up table, such that if the destination address associated with data reaching the bridge is not found in the look-up table, this is taken to imply that the receiving network is different from the sending network and that data must therefore be passed by the bridge to the non-sending network.
Data communications systems are international in scope and must be able to pass data correctly from one part of the world to any other part thereof. Typically, local area networks (LANs) communicate with each other via an FDDI network which itself is a particular type of LAN having a high bandwidth and permitting very fast data transfer.
Obviously, in such a comprehensive arrangement each node in all of the LANs as well as each node in the FDDI must have its own, unique source address. The source address of a network node is established by the manufacturer thereof, each manufacturer having at his disposal a batch of source addresses which he allocates successively to each network node during manufacture. In order to guarantee that the source address allocated by one manufacturer will not inadvertently clash with the source address allocated by a different manufacturer, it is standard to identify each manufacturer with a different index, which is then concatenated by a code given by the manufacturer in order to generate the source address associated with each network node. Since the index associated with different manufacturers is different, it follows that even if the manufacturer codes themselves coincide, the concatenated code constituting the source address must, inevitably, be unique.
However, in order that such a scheme may provide a sufficient number of unique source addresses to accommodate all known communications systems and to allow for projected reasonable expansion thereof, it follows that the number of bits of binary data associated with each code generated by the manufacturer must be very large indeed. Additionally, in order not to restrict unduly the number of competing manufacturers, the index code allotted to each different manufacturer must likewise have a sufficient number of different permutations. Both of these desiderata result in the fact that source addresses associated with such networks contain a very large number of binary data bits. Typically, 48 binary data bits are used in order to accommodate each unique source address.
If such a large number of binary data bits is to be stored in the look-up table associated with each bridge in the data communications system, then it is clear that extremely high capacity memory is required.
A further requirement of look-up tables in network bridges is that data access time must be very fast, typically in the order of several hundred nano-seconds. Thus, if each source address is stored in a random access memory (RAM) having a plurality of addressable locations each containing 48 bits of data, then in order to determine whether a particular address is stored therein, each addressable location must be read sequentially, the contents of each addressable location being logically processed in order to determine whether they correspond to the required address. This is clearly a time-consuming process.
Therefore, it is known to use a contents addressable memory (CAM) which contain on-chip logic to permit, in effect, all the addressable memory locations therein to be scanned simultaneously in order to establish whether a particular address is stored therein. However, a major drawback of CAMs is that they are expensive: typically U.S.$20 for a CAM having 256 addressable locations each containing 48 bits. Clearly, then, using CAMs to build even a moderately sized look-up table requiring maybe 100 or more CAMs would be prohibitively expensive.
It is known that data communications systems are dynamic and since the capacity of the look-up table is necessarily finite and memory is at a premium, destination addresses stored in the look-up table which are not used for a predetermined time period, should be deleted from the look-up table so as to leave room for the storage of destination addresses relating to actual usage. In a practical system, this is accomplished by associating an aging flag with each destination address stored in the look-up table, the aging flag typically comprising a plurality of memory data bits which are either decremented or incremented during successive time periods until the aging flag reaches a lower or upper threshold, whereupon the addressable location in the look-up table associated with that destination address becomes available for the storage of new data. Obviously, each time a new address is stored in the look-up table, the corresponding aging flag is initialized and each time the look-up table is scanned for a particular destination address which is found therein, the aging flag must likewise be reinitialized.
Since, under certain circumstances, it may be required not to delete destination addresses from the look-up table, regardless of their aging flag, a write-protect mechanism may also be employed so as to specify that the associated data is write-protected and must never be over-written.
Clearly, the provision of a write-protect mechanism as well as an aging flag requires yet additional binary data bits which still further increase the required capacity of the look-up table.